import java.io.BufferedReader;
import java.text.CollationElementIterator;
import java.time.LocalDate;
import java.util.*;

public class SortTest {
    public static void main(String[] args) {
        int[] arr = new int[10000];
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < 10000; i++) {
            list.add(i);
        }
        Collections.shuffle(list);
        for (int i = 0; i < 10000; i++) {
            arr[i] = list.get(i);
        }

        System.out.println("排序前");
        long begin = System.currentTimeMillis();
        System.out.println(Arrays.toString(arr));
        //BubbleSort(arr);
        //selectSort(arr);
        //insertSort(arr);
        //shellSort(arr);
        //quickSort(arr);
        mergeSort(arr);
        System.out.println("排序后");
        System.out.println(Arrays.toString(arr));
        long end = System.currentTimeMillis();
        System.out.println(end - begin);
    }


    public static void mergeSort(int[] arr){
        mergeSeparate(arr,0,arr.length-1);
    }
    // 归
    public static void mergeSeparate(int[] arr,int left,int right){
        if(left >= right){
            return;
        }
        int mid = (left+right)/2;

        mergeSeparate(arr,left,mid);
        mergeSeparate(arr,mid+1,right);
        merge(arr,left,right,mid);
    }
    // 并
    public static void merge(int[] arr,int left ,int right,int mid){
        int[] array = new int[right-left+1];
        int i = left;
        int j = mid+1;
        int k = 0;
        while(i<=mid && j<=right){
            while(i<=mid && arr[i] <= arr[j]){
                array[k++] = arr[i++];
            }
            while(j<=right && arr[j] <= arr[i]){
                array[k++] = arr[j++];
            }
        }
        while(i <= mid){
            array[k++] = arr[i++];
        }
        while(j <= mid){
            array[k++] = arr[j++];
        }

        // 将新数组中的元素拷贝到老数组中
        for (int l = 0; l < array.length; l++) {
            arr[left++] = array[l];
        }
    }






    /**
     * 快速排序
     */
    public static void quickSort(int[] arr){
        quick(arr,0,arr.length-1);
    }
    public static void quick(int[] arr,int left,int right){
        if(left >= right){
            return;
        }
        int pivot = partition(arr,left,right);

        // 向左递归
        quick(arr,left,pivot-1);
        // 向右递归
        quick(arr,pivot+1,right);
    }

    // 分区 返回基准下标 方便下一次进行递归
    private static int partition(int[] arr,int left,int right){
        int pivot = arr[left];
        int i = left;
        int j = right;
        while (left < right) {
            while (left < right && arr[right] >= pivot) {
                right--;
            }

            while (left < right && arr[left] <= pivot) {
                left++;
            }
            swap(arr, left, right);
        }
        swap(arr, left, i);
        return left;
    }




    /**
     * 冒泡排序
     * @param arr
     */
    public static void BubbleSort(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            boolean flag = false;
            for (int j = 0; j < arr.length-1 -i; j++) {
                if(arr[j] > arr[j+1]){
                    swap(arr,j,j+1);
                    flag = true;
                }
            }
            if(!flag){
                break;
            }
            System.out.println("第"+(i+1)+"轮");
            System.out.println(Arrays.toString(arr));
        }
    }

    public static void selectSort(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            // 默认认为i下标的元素为最小值
            int minIndex = i;
            for (int j = i+1; j < arr.length; j++) {
                if(arr[j] < arr[minIndex]){
                    // 碰见更小的元素,更新minIndex的值
                    minIndex = j;
                }
            }
            swap(arr,i,minIndex);
        }
    }


    public static void insertSort(int[] arr){
        for (int i = 1; i < arr.length; i++) {
            // 当前要插入的元素
            int cur = arr[i];

            int j;
            for (j = i-1; j >=0; j--) {
                if(cur >= arr[j]){
                    break;
                }else{
                    arr[j+1] = arr[j];
                }
            }
           arr[j+1] = cur;
        }
    }

    public static void shellSort(int[] arr){
        // 分组
        for (int gap = arr.length/2; gap >= 1; gap = gap/2) {
            // 遍历每一个分组
            for (int i = gap; i < arr.length; i++) {
                int cur = arr[i];
                int j;
                for ( j = i - gap; j >=0 ; j-=gap) {
                    if(arr[j] > cur){
                        arr[j+gap] = arr[j];
                    }else{
                        break;
                    }
                }
                arr[j+gap] = cur;
            }
        }
    }


    public static void swap(int[] arr,int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
